package top101K.linkedList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Author quan
 * @Description 请判断该链表是否为回文结构。
 * 回文是指该字符串正序逆序完全一致。1221 true; 12 false
 * 方法2中的子链表的反转没看懂
 * @Date 2023/8/1 20:29
 */
public class Demo13_IsPail {
    /**
     * 链表是单向的，没有办法解决；依辅助工具数组来实现。
     * 遍历链表，将链表的值都取出来放在一个数组1中；然后将数组1中的值放在数组2中并进行反转；最后比较数组1与数组2中的值是否相等。
     * 优化：在一个数组上直接在首尾用双指针操作。
     * @param head
     * @return
     */
//    public boolean isPail (ListNode head) {
//        ArrayList<Integer> nums = new ArrayList();
//        //将链表元素取出一次放入数组
//        while(head != null){
//            nums.add(head.val);
//            head = head.next;
//        }
//        ArrayList<Integer> temp = new ArrayList();
//        temp = (ArrayList<Integer>) nums.clone();
//        //准备一个数组承接翻转之后的数组
//        Collections.reverse(temp);
//        for(int i = 0; i < nums.size(); i++){
//            int x = nums.get(i);
//            int y = temp.get(i);
//            //正向遍历与反向遍历相同
//            if(x != y)
//                return false;
//        }
//        return true;
//    }

    /**
     * 一开始的思路就是这样，
     * 思路：先求出链表长度，遍历到链表中间节点位置，从中间位置开始对后半段子链表进行反转。
     * 双指针左指针指向链表开头，右指针指向链表尾部，左指针从前前往后遍历，右指针从后往前遍历？（这怎么遍历）
     * 依次比较对应位置的元素值是否相等。
     * 优化：对找中间点的优化：慢指针每次走一个节点，快指针每次走两个节点，快指针到达链表尾的时候，慢指针刚好到了链表中点。
     * @param head
     * @return
     */
    public boolean isPail (ListNode head) {
        //求链表长度
        int count = 0;
        ListNode pre = head;
        while (pre!=null){
            pre = pre.next;
            count++;
        }
        //找到链表中点位置
        int mid = count/2;
        //遍历到链表中间
        while (mid>0){
            pre = pre.next;
            mid--;
        }
        //将中点后面一段的子链表进行反转：
        // 如果是4个数，pre指向第三个数字，从第三个数字开始反转；如果是5个数，pre也是指向第3个数字，从第三个数字开始反转
        ListNode right = reverse(pre);
        //比较后的子链表与前半段子链表的值是否相等
        ListNode left = head;
        while (right!=null){
            if(right.val!=left.val){
                return false;
            }
            right = right.next;
            left = left.next;
        }
        return true;
    }

    /**
     * 传入子链表头结点，返回反转后的子链表:这里没看懂！
     * @param head 子链表的头结点
     * @return
     */
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head!=null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
